package com.ryujung.number.leetCode_258;

/**
 * Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Example:

Input: 38
Output: 2 
Explanation: The process is like: 3 + 8 = 11 -> 1 + 1 = 2. 
             Since 2 has only one digit, return it.
Follow up:
Could you do it without any loop/recursion in O(1) runtime?


思路:假设一个三位数整数n=100*a+10*b+c,变化后addn=a+b+c；
两者的差值n-addn=99a+9b，差值可以被9整除，说明每次缩小9的倍数
那么我们可以对res=num%9，若不为0则返回res，为0则返回9
 */

/**
 * 递归解法(暴力法)
 * 思路:
 * 1.判断num是否>9,否则返回num
 * 2.定义一个sum=0,来累加每一位的数之和.
 * 2.获取num的个位的值,并将num除10取整,
 * 3.循环判断取整后的num是否大于9,否则继续第2步
 * 4.判断sum是否大于9,
 */
public class Solution {
    public static int addDigits(int num) {
        int sum = 0;
        while (num > 9) {
            sum += num % 10;
            num /= 10;
        }
        sum += num;

        if (sum > 9) {
            sum = addDigits(sum);
        }
        return sum;
    }

    /**
     * 找规律:
    原数: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
    数根: 1 2 3 4 5 6 7 8 9  1  2  3  4  5  6  7  8  9  1  2  3  4  5  6  7  8  9  1  2  3 
      1 2 3 4 5 6 7 8 0   取模， 9是错误的，解决办法：将9减去1取模，再+1后作为结果，要考虑0是否需要单独判断
     */
    public static int addDigits2(int num) {
        // return num%9; num=9时应该为9
        return (num - 1) % 9 + 1;
    }

    public static void main(String[] args) {
        int num = 0;
        System.out.println(addDigits(num));
        System.out.println(addDigits2(num));
    }
}
/*
在数学中，数根(又称位数根或数字根Digital root)是自然数的一种性质，换句话说，每个自然数都有一个数根。

数根是将一正整数的各个位数相加（即横向相加），若加完后的值大于10的话，则继续将各位数进行横向相加直到
其值小于十为止[1]，或是，将一数字重复做数字和，直到其值小于十为止，则所得的值为该数的数根。

例如54817的数根为7，因为5+4+8+1+7=25，25大于10则再加一次，2+5=7，7小于十，则7为54817的数根。

找规律:
原数: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
数根: 1 2 3 4 5 6 7 8 9  1  2  3  4  5  6  7  8  9  1  2  3  4  5  6  7  8  9  1  2  3 

*/